package algorithm_demo.leetcode;

/**
 * 42. 接雨水
 * <a href="https://leetcode.cn/problems/trapping-rain-water/">https://leetcode.cn/problems/trapping-rain-water/</a>
 * @author Api
 * @date 2023/5/9 0:37
 */
public class Problem_042_TrappingRainWater {
    public int trap(int[] height) {
        //异向指针
        int left = 0;
        int right = height.length-1;
        int water = 0;
        int leftMax = 0;
        int rightMax = 0;
        while(left < right){
            leftMax = Math.max(leftMax, height[left]);
            rightMax = Math.max(rightMax, height[right]);
            if(height[left] > height[right]){
                water += rightMax-height[right];
                right--;
            }else{
                water += leftMax-height[left];
                left++;
            }
        }
        return water;
    }
}
